package Leetcode第一期;

import java.util.*;

/**
 * @author : K k
 * @date : 10:26 2020/9/11
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 * 说明：
 *
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 *
 * 输入: k = 3, n = 7
 * 输出: [[1,2,4]]
 * 示例 2:
 *
 * 输入: k = 3, n = 9
 * 输出: [[1,2,6], [1,3,5], [2,3,4]]
 *
 */
public class 组合总和III_216 {
    List<List<Integer>> lists=new ArrayList<>();
    Deque<Integer> deque=new LinkedList<>();

    //思路相同：回溯
    public List<List<Integer>> combinationSum3(int k, int n) {
        if (n<0||k<0) {return lists;}

        //总和为n的k位数组合
        dfsSolver(k,n,1);
        return lists;
    }

    private void dfsSolver(int k, int n, int start) {
        if(start>10 ||deque.size()>k) {return;}
        if (n==0 && deque.size()==k){
            lists.add(new ArrayList<>(deque));
            return;
        }

        for (int i=start;i<10;i++){
            deque.addLast(i);
            dfsSolver(k,n-i,i+1);
            deque.removeLast();
        }
    }
}
